package addressBook;

import java.util.Stack;

/**
 * @author Jarvan
 * @version 1.0
 * @create 2020/11/12 21:44
 */
public class BinarySearchTree<E extends Comparable<E>> {

    private TreeNode<E> root;

    public BinarySearchTree() {
        root = null;
    }

    /**
     * 增
     */
    private boolean insertItem(E element) {
        TreeNode<E> node = new TreeNode<>();
        node.setElement(element);
        //第一个插入的元素为根节点.
        if (root == null) {
            this.root = node;
            return true;
        }
        while (root != null){
            int elemCompareRoot = element.compareTo(root.element);
            //小的node插入到左子树中
            if (elemCompareRoot < 0){
                //叶子节点就插入
                if (root.left == null){
                    root.left = node;
                    return true;
                }
                else {
                    //不是叶子节点就继续，直到叶子节点
                    root = root.left;
                }
            }//大的node就插入到右子树中
            else if (elemCompareRoot > 0){
                //如果是叶子节点就插入
                if (root.right == null) {
                    root.right = node;
                    return true;
                }else{
                    //如果不是叶子节点就继续，直到叶子节点
                    root = root.right;
                }
            }
        }
        //二个元素完全相等
        return false;
    }

    /**
     * 查
     */
    private TreeNode<E> searchItem(E contactKey) {
        while (root != null) {
            //小的节点继续左子树
            if (contactKey.compareTo(root.element) < 0){
                root = root.left;
            }//大的节点继续右子树
            else if (contactKey.compareTo(root.element) > 0){
                root = root.right;
            } //相等就返回结果
            else if (contactKey.compareTo(root.element) == 0) {
                return root;
            }
        }
        //遍历到根节点还找不到，就查找失败.
        return null;
    }
    /**
     *  删
     */
    private boolean removeElement(E removeElement) {
        if (root != null){
            //使用之前的二叉树查找找到删除节点
            TreeNode<E> searchItem = searchItem( removeElement);
            //1.叶子节点
            if (searchItem.left == null && searchItem.right == null) {
                searchItem = null;
                return true;
            }
            //2.只有左子树或者右子树
            else if (searchItem.left == null){
                searchItem.element = searchItem.right.element;
                if (searchItem.right.right!=null){
                    searchItem.right = searchItem.right.right;
                }
                if (searchItem.right.left != null){
                    searchItem.left = searchItem.right.left;
                }
                return true;
            }else if (searchItem.right == null){
                searchItem.element = searchItem.left.element;
                if (searchItem.left.right !=null){
                    searchItem.right = searchItem.left.right;
                }
                if (searchItem.left.left !=null){
                    searchItem.left = searchItem.left.left;
                }
                return true;
            }else {
                //【重点】3. 有左子树和右子树

                //3.1 找到继承者的父节点
                TreeNode<E> successorParent = findSuccessorParent(searchItem);
                //3.2 替换删除节点的值为继承者的值
                searchItem.element = successorParent.left.element;
                //3.3 删除继承，
                // 如果继承者是不是叶子
                if (successorParent.left.right !=null){
                    successorParent.left = successorParent.left.right;
                }
                //继承者是叶子的时候. 删除
                else {
                    successorParent.left = null;
                }
                return true;

            }

        }
        return false;
    }
    private TreeNode<E> findSuccessorParent(TreeNode<E> currentNode){
        TreeNode<E> node = currentNode;
        TreeNode<E> parent;
        Stack<TreeNode<E>> stack = new Stack<>();
        while (node!=null || !stack.isEmpty()){
            while (node != null){
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()){
                stack.pop();
                //使用中序遍历的方式找到继承者的父节点.
                return stack.pop();
            }

        }
        return null;
    }

    /**
     * 迭代器
     */
    public TreeIterator<E> iterator() {
        return new TreeIterator<E>(this.root);
    }

}
